The disclosure in the compact disc appendix of this patent disclosure of this patent document contains material to which a claim of copyright protection is made. The copyright owner grants the right to third parties for facsimile reproduction of any one of the patent documents or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but reserves any and all other rights whatsoever not expressly granted herein.
The invention relates generally to the field of image processing, and in particular to embedding and extracting hidden messages in digital image data. This field is also referred to as data hiding, information hiding, watermarking and also steganography.
U.S. patent application Ser. No. 08/848,112, filed Apr. 28, 1997 and allowed Sep. 23, 1999, entitled xe2x80x9cMethod For Generating An Improved Carrier For Use In An Image Data Embedding Application,xe2x80x9d by Honsinger et al., discloses a technique for embedding messages in digital images data. This method for embedding a hidden message into a digitized image includes the steps of: forming a digitized version of the desired message; generating a random phase carrier; convolving the digitized version of the desired message and the random phase carrier to form a dispersed message; and combining the dispersed message with the digitized image to form an embedded hidden message image. Hidden messages may be embedded in photographic images recorded on film and paper using conventional photographic printing techniques, or they may be embedded in images produced on printers such as ink jet and thermal dye transfer printers, by combining the dispersed message with a digital image using digital image processing techniques.
The hidden messages are recovered from the embedded hidden message image by cross correlating the embedded hidden message image containing the dispersed message with a decoding carrier to recover the embedded dispersed message; and extracting the digital message data from the recovered dispersed message.
One known technique for extracting a dispersed message when the image has been cropped and/or rotated employs, a separate calibration signal contained in the image. Once the calibration signal was found, it is used to determine the dispersed message boundaries and the knowledge of the boundaries is employed to extract the message from the image. Such a technique is described in U.S. Pat. No. 5,850,481 issued Dec. 15, 1998 to Rhoads.
One problem with adding a calibration signal to an image is that it takes extra bandwidth that could be used for other purposes such as storing more information in the hidden message. There is a need therefore for an improved method of identifying the dispersed message boundaries without the need for a separate calibration signal to aid in extraction of the dispersed message.
The present invention is directed at overcoming the need for a calibration signal to find the message boundary in an embedded message. Briefly summarized, according to one aspect of the present invention a method for extracting an embedded message from a digital image, the embedded message being formed by convolution with a carrier, employs a message template indicating the relative locations of data in the embedded message, the relative locations of the data being such that the autocorrelation of the message template is strongly peaked. An arbitrary region of the digital image is correlated with the carrier to extract a cyclically shifted message from the digital image. The absolute value of the cyclically shifted message is taken to form a positive valued cyclically shifted message. The positive valued cyclically shifted message is correlated with the message template to form a shifted offset image having a peak amplitude representing the location of the message boundary. The location of the message boundary is employed to extract the hidden message.
The present invention has the advantage of avoiding the need for calibration signals to indicate the location of the embedded data in the image.